package _1_3_Collections;

import _1_2_ClassAndObject.User;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * java.util.ArrayList 与 Arrays.ArrayList {@link LinkedList#get(int)}
 * <p>
 * {@link ArrayList#get(int)} 遍历方法 {@link LinkedList#node(int)}
 * <p>
 * {@link LinkedList#add(int, Object)}}     {@link ArrayList#add(int, Object)}}
 * <p>
 * {@link LinkedList#add(Object)}}          {@link ArrayList#add(Object)}}
 */
public class AboutList {

  private int addLimit = 50000;
  private LinkedList<User> linkedList;
  private ArrayList<User> arrayList;
  private User user;

  /*
                                  ArrayList                   LinkedList
  get(int index)方法：                快                          慢
                原因：      根据index直接得到内存地址       调用了遍历方法查找，越靠近中间越慢

  add()  头部插入   :          list越大，插入越慢                  稍快
                原因：      头/尾插入，直接添加一个元素      尾部新增，直接改变头部指针
                           数组复制的方式移位耗时稍多
                           native方法拷贝，不很慢

  add()  中间插入   :           快                                 慢
                        定位插入位置快，移位操作没那么多      遍历链表指针（二分查找）耗时多

  add()  尾部插入   :           几乎一样快                         几乎一样快
                        定位插入位置快，没有移位操作          仅仅改变last指针


  remove 同理

  LinkedList 的 node(int) 遍历方法：
         因为：在内存中的数据结构不同，链表需要一个一个的向下或向上遍历，最终得到内存地址
             例如：jdk的 {@link LinkedList#get(int)} 的具体实现：{@link LinkedList#node(int)}
             可见，LinkedList的get(int index)方法，index越在链表中间，方法越耗时 {@link #linkedListGetMethod()}

   */
  @Test
  public void compareLinkedListWithArrayList() {
    compareHeadAdd();
    System.out.println();
    compareMiddleAdd();
    System.out.println();
    compareTailAdd();
  }

  /**
   * list for 循环的不同写法, 提高效率, list长度较短时不明显 TODO 添加到目录
   */
  @Test
  public void forILoopInList() {
    List<String> list = new ArrayList<>();
    for (int i = 0; i < 10000; i++) {
      list.add(String.valueOf(i));
    }

    long start = System.currentTimeMillis();
    for (int i = 0; i < 100; i++) {
      for (int i1 = 0; i1 < list.size(); i1++) {
        Integer i11 = Integer.valueOf(list.get(i1));
        // 在方法体中再次用到了 list.size()方法，此时可以按下面的写法
        int i2 = i11 + list.size();
      }
    }
    System.out.println("ArrayList    for循环  耗时：" + (System.currentTimeMillis() - start) + "ms");

    start = System.currentTimeMillis();
    for (int i = 0; i < 100; i++) {
      for (int i1 = 0, length = list.size(); i1 < length; i1++) {
        Integer i11 = Integer.valueOf(list.get(i1));
        int i2 = i11 + length;
      }
    }
    System.out.println("ArrayList    for循环  耗时：" + (System.currentTimeMillis() - start) + "ms");
  }

  /**
   * 把 List 分割为多个 List TODO 添加到目录
   */
  @Test
  public void splitList() {
    List<Integer> origin = new ArrayList<>(35);
    for (int i = 0; i < 35; i++) {
      origin.add(i);
    }
    origin.clear();

    int groupSize = 8;
    int group = (origin.size() + groupSize - 1) / groupSize;
    for (int i = 0; i < group; i++) {
//            List<Integer> integers = origin.subList(i * groupSize, (i + 1 == group) ? origin.size() : (i + 1) * groupSize);
//            for (Integer integer : integers) {
//                System.out.println(integer);
//            }
      int start = i * groupSize;

      for (int j = 0; j < groupSize; j++) {
        Integer every = origin.get(start + j);
        System.out.println(every);
      }
    }
  }

  /**
   * set(index, Object) 方法, 必须在 List 有这个 index 之后才能使用
   */
  @Test
  public void listSetValueOfIndex() {
    List<String> list = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
      list.add(String.valueOf(i));
    }
    list.set(5, "没错");
    System.out.println(list.get(5));

    list = new ArrayList<>(10);
    list.set(0, "出错");

    list = new ArrayList<>(10);
    list.set(1, "出错");
  }

  /**
   * 可以看出 LinkedList的get方法，越在链表中间的元素，get()方法的耗时越长
   */
  @Test
  public void linkedListGetMethod() {
    System.out.println("****************  LinkedList   get() 测试****************");
    LinkedList<String> linkedList = new LinkedList<>();
    int addLimit = 100000;
    for (int j = 0; j < addLimit; j++) {
      linkedList.add("linked" + j);
    }
    System.out.println("LinkedList   size: " + addLimit);

    long start = System.currentTimeMillis();
    int index = addLimit / 2;
    for (int i = 0; i < 1000; i++) {
      String s = linkedList.get(index);
    }
    System.out.println("LinkedList   get(列表size/2) 耗时：" + (System.currentTimeMillis() - start) + "ms");
    start = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++) {
      String s = linkedList.get(1);
    }
    System.out.println("LinkedList   get(1)          耗时：" + (System.currentTimeMillis() - start) + "ms");
  }

  /**
   * 头部插入：linkedList 只需要改一个指针，arrayList要复制所有元素到新的数组， 所以数组越大，arrayList头部插入越慢
   */
  private void compareHeadAdd() {
    System.out.println("****************  比较 add() 方法：头部插入 ****************");
    prepareList();

    long start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      linkedList.add(0, user);
    }
    System.out.println("LinkedList   add() 头部插入耗时：" + (System.currentTimeMillis() - start) + "ms");

    start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      arrayList.add(0, user);
    }
    System.out.println("ArrayList    add() 头部插入耗时：" + (System.currentTimeMillis() - start) + "ms");
  }

  /** 比较尾部插入 */
  private void compareTailAdd() {
    System.out.println("****************  比较 add() 方法：尾部插入 ****************");
    prepareList();

    long start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      linkedList.add(user);
    }
    System.out.println("LinkedList   add() 尾部插入耗时：" + (System.currentTimeMillis() - start) + "ms");

    start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      arrayList.add(user);
    }
    System.out.println("ArrayList    add() 尾部插入耗时：" + (System.currentTimeMillis() - start) + "ms");
  }

  /** 比较中间插入 */
  private void compareMiddleAdd() {
    System.out.println("****************  比较 add() 方法：中间插入 ****************");
    prepareList();

    long start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      linkedList.add((addLimit + i) / 2, user);
    }
    System.out.println("LinkedList   add() 中间插入耗时：" + (System.currentTimeMillis() - start) + "ms");

    start = System.currentTimeMillis();
    for (int i = 0; i < addLimit; i++) {
      arrayList.add((addLimit + i) / 2, user);
    }
    System.out.println("ArrayList    add() 中间插入耗时：" + (System.currentTimeMillis() - start) + "ms");
  }

  private void prepareList() {
    user = new User();
    user.setAge(1);
    linkedList = new LinkedList<>();
    arrayList = new ArrayList<>();
    for (int i = 0; i < addLimit; i++) {
      arrayList.add(user);
    }
    for (int i = 0; i < addLimit; i++) {
      linkedList.add(user);
    }
  }
}
